Network Volume Anomaly Detection and Identification in Large-scale Networks based on Online Time-structured Traffic Tensor Tracking

摘要

This paper addresses network anomography, that is, the problem of inferringnetwork-level anomalies from indirect link measurements. This problem is castas a low-rank subspace tracking problem for normal flows under incompleteobservations, and an outlier detection problem for abnormal flows. Sincetraffic data is large-scale time-structured data accompanied with noise andoutliers under partial observations, an efficient modeling method is essential.To this end, this paper proposes an online subspace tracking of a Hankelizedtime-structured traffic tensor for normal flows based on the Candecomp/PARAFACdecomposition exploiting the recursive least squares (RLS) algorithm. Weestimate abnormal flows as outlier sparse flows via sparsity maximization inthe underlying under-constrained linear-inverse problem. A major advantage isthat our algorithm estimates normal flows by low-dimensional matrices withtime-directional features as well as the spatial correlation of multiple linkswithout using the past observed measurements and the past model parameters.Extensive numerical evaluations show that the proposed algorithm achievesfaster convergence per iteration of model approximation, and better volumeanomaly detection performance compared to state-of-the-art algorithms.